Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

XFuNTreePostOrderIterator.h

Go to the documentation of this file.
00001 /*! \file 
00002  * X-Forge Util <br>
00003  * Copyright 2000-2003 Fathammer Ltd
00004  * 
00005  * \brief N-Tree post-order iterator template
00006  *
00007  * $Id: XFuNTreePostOrderIterator.h,v 1.6 2003/03/20 13:19:59 jetro Exp $
00008  * $Date: 2003/03/20 13:19:59 $
00009  * $Revision: 1.6 $
00010  */
00011 
00012 #ifndef XFUNTREEPOSTORDERITERATOR_H_INCLUDED
00013 #define XFUNTREEPOSTORDERITERATOR_H_INCLUDED
00014 
00015 #include <xfutil/XFuNTreeAbstractIterator.h>
00016 #include <xfutil/XFuDynamicArray.h>
00017 
00018 template<class T> class XFuNTree;
00019 template<class T> class XFuNTreeNode;
00020 
00021 
00022 template<class T> class XFuNTreePostOrderIterator : public XFuNTreeAbstractIterator<T>
00023 {
00024 public:
00025     
00026     //! Assignment operator overload.
00027     void operator=(const XFuNTreePostOrderIterator &aClone);
00028 
00029     //! Advances to the next node, pre-operation.
00030     /*!
00031      * \return Reference to next node.
00032      */
00033     XFuNTreePostOrderIterator<T> & operator++();
00034     
00035     //! Advances to the next node, post-operation.
00036     /*!
00037      * \return Next node.
00038      */
00039     XFuNTreePostOrderIterator<T> operator++(int);
00040 
00041     //! Creates an empty iterator.
00042     XFuNTreePostOrderIterator();
00043     //! Creates an iterator pointing to a node.
00044     XFuNTreePostOrderIterator(XFuNTreeNode<T> *aNode, const UINT32 aNodes, 
00045         const UINT32 aChildNodes);
00046     //! Clones an iterator.
00047     XFuNTreePostOrderIterator(const XFuNTreePostOrderIterator<T> &aClone);
00048 
00049     //! Destructor.
00050     ~XFuNTreePostOrderIterator();
00051     
00052 protected:
00053     
00054     //! Number of nodes in tree.
00055     UINT32 mNodes;
00056 
00057     //! Stack used for saving pointers to nodes.
00058     XFuDynamicArray<XFuNTreeNode<T> *> *mNodeStack;
00059     //! Stack used for saving information on visitation of node.
00060     XFuDynamicArray<INT> *mBoolStack;
00061 };
00062 
00063 
00064 template<class T>
00065 void XFuNTreePostOrderIterator<T>::operator=(
00066     const XFuNTreePostOrderIterator &aClone)
00067 {
00068     mNode = aClone.mNode;
00069     mNodes = aClone.mNodes;
00070     mChildNodes = aClone.mChildNodes;
00071 
00072     if ((aClone.mNodeStack != NULL) && (aClone.mBoolStack != NULL))
00073     {
00074         if (mNodeStack == NULL)
00075             mNodeStack = XFuDynamicArray<XFuNTreeNode<T> *>::create(
00076                 aClone.mNodeStack->maxSize());
00077 
00078         if (mBoolStack == NULL)
00079             mBoolStack = XFuDynamicArray<INT>::create(
00080                 aClone.mBoolStack->maxSize());
00081 
00082         if ((mNodeStack == NULL) || (mBoolStack == NULL))
00083         {
00084             mNode = NULL;
00085             mNodes = 0;
00086             mChildNodes = 0;
00087             return;
00088         }
00089 
00090         UINT32 i, lastElement;
00091         XFuNTreeNode<T> *temp = NULL;
00092         INT boolTemp;
00093 
00094         lastElement = aClone.mNodeStack->size();
00095         for (i = 0; i < lastElement; ++i)
00096         {
00097             temp = aClone.mNodeStack->get(i);
00098             mNodeStack->put(i, temp);
00099         }
00100 
00101         lastElement = aClone.mBoolStack->size();
00102         for (i = 0; i < lastElement; ++i)
00103         {
00104             boolTemp = aClone.mBoolStack->get(i);
00105             mBoolStack->put(i, boolTemp);
00106         }
00107     }
00108     else
00109     {
00110         if (mNodeStack != NULL)
00111         {
00112             delete mNodeStack;
00113             mNodeStack = NULL;
00114         }
00115 
00116         if (mBoolStack != NULL)
00117         {
00118             delete mBoolStack;
00119             mBoolStack = NULL;
00120         }
00121     }
00122 }
00123 
00124 
00125 template<class T>
00126 XFuNTreePostOrderIterator<T> & XFuNTreePostOrderIterator<T>::operator++()
00127 {
00128     if (!mNodeStack->isEmpty())
00129     {
00130         mNode = mNodeStack->remove();
00131         INT temp = mBoolStack->remove();
00132 
00133         if (!temp)
00134         {
00135             UINT32 i, j;
00136 
00137             while (!mNode->isLeaf())
00138             {
00139                 mNodeStack->put(mNode);
00140                 mBoolStack->put(1);
00141 
00142                 for (j = 0; j < mChildNodes; ++j)
00143                 {
00144                     if (mNode->isValid(j))
00145                     {
00146                         for (i = (mChildNodes - 1); i > j; --i)
00147                         {
00148                             if (mNode->isValid(i))
00149                             {
00150                                 mNodeStack->put(mNode->getChild(i));
00151                                 mBoolStack->put(0);
00152                             }
00153                         }
00154 
00155                         mNode = mNode->getChild(j);
00156                         break;
00157                     }
00158                 }
00159             }
00160         }
00161     }
00162     else
00163     {
00164         mNode = NULL;
00165     }
00166 
00167     return *this;
00168 }
00169 
00170 
00171 template<class T>
00172 XFuNTreePostOrderIterator<T> XFuNTreePostOrderIterator<T>::operator++(int)
00173 {
00174     XFuNTreePostOrderIterator<T> newIt = XFuNTreePostOrderIterator<T>(*this);
00175 
00176 /*
00177     if (mNode != NULL) mNode = mNode->mNext;
00178 
00179     return newIt;
00180 */
00181 }
00182 
00183 
00184 template<class T> XFuNTreePostOrderIterator<T>::XFuNTreePostOrderIterator()
00185 {
00186     mNode = NULL;
00187     mNodes = 0;
00188     mChildNodes = 0;
00189     mNodeStack = NULL;
00190     mBoolStack = NULL;
00191 }
00192 
00193 
00194 template<class T> 
00195 XFuNTreePostOrderIterator<T>::XFuNTreePostOrderIterator(XFuNTreeNode<T> *aNode,
00196                                                         const UINT32 aNodes,
00197                                                         const UINT32 aChildNodes)
00198 {
00199     if (aNode != NULL)
00200     {
00201         mNode = aNode;
00202         mNodes = aNodes;
00203         mChildNodes = aChildNodes;
00204 
00205         mNodeStack = XFuDynamicArray<XFuNTreeNode<T> *>::create(aNodes);
00206         mBoolStack = XFuDynamicArray<INT>::create(aNodes);
00207 
00208         if ((mNodeStack == NULL) || (mBoolStack == NULL))
00209         {
00210             mNode = NULL;
00211             mNodes = 0;
00212             mChildNodes = 0;
00213         }
00214         else
00215         {
00216             UINT32 i, j;
00217 
00218             while (!mNode->isLeaf())
00219             {
00220                 mNodeStack->put(mNode);
00221                 mBoolStack->put(1);
00222 
00223                 for (j = 0; j < mChildNodes; ++j)
00224                 {
00225                     if (mNode->isValid(j))
00226                     {
00227                         for (i = (mChildNodes - 1); i > j; --i)
00228                         {
00229                             if (mNode->isValid(i))
00230                             {
00231                                 mNodeStack->put(mNode->getChild(i));
00232                                 mBoolStack->put(0);
00233                             }
00234                         }
00235 
00236                         mNode = mNode->getChild(j);
00237                         break;
00238                     }
00239                 }
00240             }
00241         }
00242     }
00243 }
00244 
00245 
00246 template<class T> 
00247 XFuNTreePostOrderIterator<T>::XFuNTreePostOrderIterator(
00248     const XFuNTreePostOrderIterator<T> &aClone)
00249 {
00250     mNode = aClone.mNode;
00251     mNodes = aClone.mNodes;
00252     mChildNodes = aClone.mChildNodes;
00253 
00254     if ((aClone.mNodeStack != NULL) && (aClone.mBoolStack != NULL))
00255     {
00256         if (mNodeStack == NULL)
00257             mNodeStack = XFuDynamicArray<XFuNTreeNode<T> *>::create(
00258                 aClone.mNodeStack->maxSize());
00259 
00260         if (mBoolStack == NULL)
00261             mBoolStack = XFuDynamicArray<INT>::create(
00262                 aClone.mBoolStack->maxSize());
00263 
00264         if ((mNodeStack == NULL) || (mBoolStack == NULL))
00265         {
00266             mNode = NULL;
00267             mNodes = 0;
00268             mChildNodes = 0;
00269             return;
00270         }
00271 
00272         UINT32 i, lastElement;
00273         XFuNTreeNode<T> *temp = NULL;
00274         INT boolTemp = NULL;
00275 
00276         lastElement = aClone.mNodeStack->size();
00277         for (i = 0; i < lastElement; ++i)
00278         {
00279             temp = aClone.mNodeStack->get(i);
00280             mNodeStack->put(i, temp);
00281         }
00282 
00283         lastElement = aClone.mBoolStack->size();
00284         for (i = 0; i < lastElement; ++i)
00285         {
00286             boolTemp = aClone.mBoolStack->get(i);
00287             mBoolStack->put(i, boolTemp);
00288         }
00289     }
00290     else
00291     {
00292         delete mNodeStack;
00293         delete mBoolStack;
00294         mNodeStack = NULL;
00295         mBoolStack = NULL;
00296     }
00297 }
00298 
00299 
00300 template<class T>
00301 XFuNTreePostOrderIterator<T>::~XFuNTreePostOrderIterator()
00302 {
00303     delete mNodeStack;
00304     delete mBoolStack;
00305 }
00306 
00307 
00308 #endif // !XFUNTREEPOSTORDERITERATOR_H_INCLUDED

   
X-Forge Documentation
Confidential
Copyright © 2002-2003 Fathammer
   
Documentation generated
with doxygen
by Dimitri van Heesch